import java.util.*;

/**
 * 677. 键值映射
 * https://leetcode-cn.com/problems/map-sum-pairs/
 */
public class Solutions_677 {
    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        int res1 = mapSum.sum("ap");  // output: 3
        System.out.println(res1);
        mapSum.insert("app", 2);
        int res2 = mapSum.sum("ap");  // output: 5
        System.out.println(res2);
    }
}

class Trie_677 {
    // 子节点
    Map<Character, Trie_677> childs = new HashMap<>();
    // 节点值
    int val;
}

/**
 * 字典树 + 哈希表 + 深度优先搜索（16ms）
 */
class MapSum {
    Trie_677 root = null;

    /** Initialize your data structure here. */
    public MapSum() {
        root = new Trie_677();
    }

    /**
     * 根据字符串在字典树中构造一条路径
     */
    public void insert(String key, int val) {
        char[] arr = key.toCharArray();
        Trie_677 curNode = root;
        for (char c : arr) {
            if (!curNode.childs.containsKey(c)) {
                // 子节点不存在时，添加子节点
                curNode.childs.put(c, new Trie_677());
            }
            // 迭代深入节点
            curNode = curNode.childs.get(c);
        }
        // 结束节点处，设置值
        curNode.val = val;
    }

    public int sum(String prefix) {
        char[] arr = prefix.toCharArray();
        Trie_677 cur = root;
        // 先找到 prefix 的结束节点（如果字符串的路径，在字典树中存在，那么结束节点就是 prefix 的最后一个字符）
        for (int i = 0; i < arr.length; i++) {
            if (!cur.childs.containsKey(arr[i])) {
                // 字典树中，该路径不存在
                return 0;
            }
            // 迭代深入节点
            cur = cur.childs.get(arr[i]);
        }
        // 再以结束节点为根节点，递归搜索
        return dfs(cur, 0);
    }

    /**
     * 就是普通的 N 叉树递归
     */
    public int dfs(Trie_677 node, int res) {
        if (node == null) {
            // 结束条件
            return res;
        }
        res += node.val;
        // 对每个子节点，进行递归
        for (Character next : node.childs.keySet()) {
            // res 用 = 而不用 +=
            res = dfs(node.childs.get(next), res);
        }
        return res;
    }
}
